import java.security.cert.CertificateParsingException;
import java.util.*;

class Solution {
//  static class ListNode {
//    int val;
//     ListNode next;
//   public ListNode() {}
//   public   ListNode(int val) { this.val = val; }
//    public ListNode(int val, ListNode next) { this.val = val; this.next = next; }
//  }
//    public static ListNode sortList(ListNode head) {
//        if(head == null){
//            return null;
//        }
//        ListNode cur = head.next;
//        ListNode curP = head;
//        while(cur!=null){
//            if(cur.val > curP.val){
//                curP = cur;
//                cur = cur.next;
//
//            }else{
//                if(head.val > cur.val){
//                    ListNode curN = cur.next;
//                    curP.next = cur.next;
//                    cur.next = head;
//                    head = cur;
//                    cur =curN;
//
//                }else{
//                    ListNode findC = head.next;
//                    ListNode findP = head;
//                    while(findC.val <= curP.val){
//                        if(findC.val <cur.val){
//                            findP = findC;
//                            findC = findC.next;
//                        }else{
//                            ListNode curNext = cur.next;
//                            curP.next = cur.next;
//                            cur.next = findC;
//                            findP.next = cur;
//                            cur = curNext;
//                            break;
//                        }
//                    }
//                }
//            }
//        }
//        return head;
//    }
//
//    public static void main(String[] args) {
//        ListNode A = new ListNode(4);
//        ListNode B = new ListNode(1);
//        ListNode C = new ListNode(2);
//        ListNode D = new ListNode(3);
////        ListNode E= new ListNode(0);
//        A.next= B;
//        B.next = C;
//        C.next = D;
////        D.next= E;
//        sortList(A);
//        System.out.println();
//
//
//
//    }
//}

//
//public class Solution {
//    /**
//     * @param colors: A list of integer
//     * @param k: An integer
//     * @return: nothing
//     */
//    public  static void sortColors2(int[] colors, int k) {
//        // write your code here
//        int n = colors.length;
//        int[] hash = new int[n-k];
//        for(int i=0; i< n ; i++){
//            hash[colors[i]]++;
//
//        }
//        int m =0;
//        for(int i =0;i<hash.length;i++){
//            while(hash[i] != 0){
//                colors[m++] = i;
//                hash[i]--;
//
//
//            }
//        }
//
//        System.out.println();
//    }
//
//    public static void main(String[] args) {
//        sortColors2(new int[]{2,1,1,2,2},2);
//
//    }
//}


        public static int takeAttendance(int[] records) {
            int n = records.length-1;
            int[] hash = new int[n+1];
            // for(int x : records){
            //     hash[x]++;
            // }
            for(int i = 0 ;i<n;i++){
                hash[records[i]]++;
            }
            for(int i = 0;i< n+1;i++){
                if(hash[i] == 0){
                    System.out.println(i);
                    return i;
                }
            }
            System.out.println();
            return -1;

        }



    public static int pivotIndex(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        // f[0] = 0;
        // g[n - 1] = 0;
        for (int i = 1; i < n; i++) {
            f[i] = f[i - 1] + nums[i - 1];

        }
        for (int i = n - 2; i >= 0; i--) {
            g[i] = g[i + 1] + nums[i + 1];
        }
        for (int i = 0; i < n; i++) {

            if (f[i] == g[i]) {
                return i;
            }
        }
        return -1;
    }


        /**
         * @param gas: An array of integers
         * @param cost: An array of integers
         * @return: An integer
         */
        public static int canCompleteCircuit(int[] gas, int[] cost) {
            // write your code here
            int n = gas.length;

            for(int i = 0;i< n;i++){
                int sum = gas[i];
                int j = (i+1)%n;
                int size = 0;
                for(;size <= n ;j =(j+1)%n){
                    if(j == 0){
                        sum-=cost[n-1];
                    }else{
                        sum-=cost[j-1];
                    }

                    if(sum < 0){
                        break;
                    }else{
                        sum += gas[j];
                        size++;
                    }

                }
                if( size > n){
                    return i;
                }
            }
            return -1;
        }
    public int tribonacci2(int n) {
        //空间优化
        //处理细节
        if(n == 0 ){
            return 0;
        }
        if(n == 1 || n == 2){
            return 1;
        }
        int a = 0 ,  b = 1 , c = 1 ,d =0;

        for(int i = 3 ; i <= n ; i++){
            d =a+b+c;
            a = b;
            b = c;
            c = d;

        }
        //4. 返回结果
        return d;

    }
    public int tribonacci(int n) {
        //1. 创建dp[] 表

        int[] dp = new int[n+1];
        //处理细节
        if(n == 0 ){
            return 0;
        }
        if(n == 1 || n == 2){
            return 1;
        }
        //2. 初始化
        dp[0] = 0;dp[1]= dp[2] = 1;

        //3. 填表
        for(int i = 3 ; i <= n ; i++){
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];

        }
        //4. 返回结果
        return dp[n];

    }

    public int jewelleryValue(int[][] frame) {

        int m = frame.length, n = frame[0].length;
        //创建 dp 表
        int[][] dp = new int[m+1][n+1];
        //无初始化 ,dp 默认都是 0

        //填表
        for(int i = 1; i <= m ; i++){
            for(int j = 1 ; j <= n ; j++){
                dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]) + frame[i-1][j-1];
            }
        }
        //返回结果
        return dp[m][n];


    }

    public int deleteAndEarn(int[] nums) {
        int n = 10001;
        int[] arr = new int[n];
        for(int x : nums) {
            arr[x] += x;
        }
        //动态规划
        int[] f = new int[n];
        int[] g = new int[n];
        //初始化
        f[0] = arr[0];
        for(int i = 1 ; i < n;i++){
            f[i] = g[i-1] + arr[i];
            g[i] = Math.max(f[i-1],g[i-1]);
        }
        //返回结果
        return Math.max(f[n-1],g[n-1]);

    }
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        //1 创建 dp 表
        int[] dp = new int[n+1];
        //2 初始化
        dp[0] = 0 ;
        //3. 填表
        int max = Integer.MIN_VALUE;
        for(int i = 1;i <= n;i++){
            dp[i] = Math.max(nums[i-1],nums[i-1] + dp[i-1]);
            max = Math.max(max,dp[i]);
        }

        return max;


    }


    /**
     * 最大字段和:
     * 分治法
     * @param nums 待求数组
     * @return
     */
    public static int maxSum1(int[] nums){
        return maxSubArray(nums,0,nums.length-1);
    }
    public static int maxSubArray(int[] nums,int left , int right){
        if(left == right) {
            return nums[left];
        }
        int mid = left + (right - left)/2;
        int leftMax = maxSubArray(nums,left,mid);
        int rightMax = maxSubArray(nums,mid+1,right);
        int midMax = midMaxSubArray(nums,left,right);
        return Math.max(Math.max(leftMax,rightMax), midMax);

    }
    public static int midMaxSubArray(int[] nums,int left , int right){
        int mid = left + (right - left)/2;
        int sumLeft = 0 ,leftMax = nums[mid];
        int sumRight = 0, rightMax = nums[mid+1];
        for(int i = mid; i >= left ;i--){
            sumLeft +=nums[i];
            leftMax = Math.max(sumLeft,leftMax);
        }
        for(int i = mid+1 ; i <= right;i++){
            sumRight += nums[i];
            rightMax = Math.max(sumRight,rightMax);
        }
        return leftMax+ rightMax;



    }
    public static void main(String[] args) {
        System.out.println(canCompleteCircuit(new int[]{1, 1, 3, 1}, new int[]{2, 2, 1, 1}));
//            Arrays.sort();
//        takeAttendance(new int[]{0});
//        int[] nums = {1,2};
//        Arrays.sort(nums,(a,b)->{
//            return b - a;
//        });
        int[] dp = new int[2];
        for (int x: dp) {
            System.out.println(x);


        }
        Set<String> hash = new HashSet<>();
       

    }
    public void sortColors(int[] nums) {
        int n = nums.length;
        int left = -1 ,right = n;
        int i = 0;
        while(i < right){
            if(nums[i] == 0){
                swap(nums,left+1,i);
                i++;
                left++;
            }else if(nums[i] == 1){
                i++;
            }else{
                swap(nums,i,right-1);
                right--;
            }
        }

    }
    public void swap(int[] nums,int i,int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    public int  qsort(int[] nums,int l ,int r,int k){
        if(l == r) return nums[l];
        int key = nums[new Random().nextInt(r-l+1)+l];//随机生成基准数
        int left =  l-1, right = r+1 , i = l;
        //数组分三块
        while(i < right){
            if(nums[i] < key){
                swap(nums,left+1,i);
                left++;
                i++;
            }else if(nums[i] == key){
                i++;
            }else{
                swap(nums,right-1,i);
                right--;
            }
        }
        int c = r - right+1 , b = right - left -1;
        if(c>= k ){
            return qsort(nums,right,r,k);
        }else if(b+c>=k){
            return key;
        }else{
            return qsort(nums,l,left,k-b-c);
        }

    }

    int[] tmp  ;
    public int[] sortArray(int[] nums) {
        tmp = new int[nums.length];
        mergeSort(nums,0,nums.length-1);
        return nums;
    }
    public void mergeSort(int[] nums,int left,int right){
        if(left >= right) return;
        //1.根据中间点划分区间
        int mid = (left + right)/2;
        //[left,mid]  [mid+1,right]
        //2. 将左右区间排个序
        mergeSort(nums,left,mid);
        mergeSort(nums,mid+1,right);
        //3.合并两个有序数组
        int l = left , r = mid+1 , i = 0;
        while(l <= mid && r <= right){
            if(nums[l] < nums[r]){
                tmp[i] = nums[l];
                i++;
                l++;
            }else{
                tmp[i] = nums[r];
                i++;
                r++;
            }
        }
        //处理没有遍历完的数组
        while(l <= mid) tmp[i++] = nums[l++];
        while(r<= right) tmp[i++] = nums[r++];
        //将数据还原到原数组中

        for(int j = left;j<=right ; j++){
            nums[j] = tmp[j-left];
        }
    }

}